package main

import (
	"fmt"
)

// 固定木桶排序
func caskSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	} else {
		num := 4
		buckets := make([][]int, num) //创造二维数组
		for i := 0; i < length; i++ {
			buckets[arr[i]-1] = append(buckets[arr[i]-1], arr[i]) //木桶计数加1
		}
		fmt.Println(buckets)
		tmppose := 0 //木桶排序
		for i := 0; i < num; i++ {
			bucketslen := len(buckets[i]) //求某一段的长度
			if bucketslen > 0 {
				copy(arr[tmppose:], buckets[i]) //拷贝数据
				tmppose += bucketslen           //定位
			}
		}

		return arr

	}
}

// 动态木桶排序
func caskSortX(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	} else {
		num := length
		max := findMax(arr)
		buckets := make([][]int, num) //创造二维数组
		for i := 0; i < length; i++ {
			index := arr[i] * (num - 1) / max               //木桶的自动分配算法
			buckets[index] = append(buckets[index], arr[i]) //木桶计数加1
		}
		fmt.Println(buckets)
		tmppose := 0 //木桶排序
		for i := 0; i < num; i++ {
			bucketslen := len(buckets[i]) //求某一段的长度
			if bucketslen > 0 {

				buckets[i] = selectSort(buckets[i]) //木桶内部数据排序

				copy(arr[tmppose:], buckets[i]) //拷贝数据
				tmppose += bucketslen           //定位
			}
		}

		return arr

	}
}

func findMax(arr []int) int {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr[0]
	} else {
		max := arr[0]

		for i := 0; i < length; i++ {
			if arr[i] > max {
				max = arr[i]
			}
		}
		return max
	}
}

func selectSort(arr []int) []int {
	length := len(arr) //数组长度
	if length <= 1 {
		return arr
	} else {
		max := 0

		for i := 0; i < length-1; i++ {
			max = i

			for j := i + 1; j < length; j++ {
				if arr[j] > arr[max] {
					max = j
				}
			}

			if max != i {
				arr[i], arr[max] = arr[max], arr[i]
			}

		}

	}
	return arr
}

// 木桶排序
func main() {
	arr := []int{1, 2, 3, 4, 4, 3, 2, 2, 3, 1}
	fmt.Println(arr)

	fmt.Println(caskSortX(arr))

}
